﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using SearchCompare;

namespace ComparisonGraph
{
    class AlgorithmComparer
    {

        public static Display GenerateMatchingGraphDisplay()
        {
            Random rng = new Random();
            Display dis = new Display(Display.DisplayType.Match);
            string text = GenerateText(100000);
            string[] patterns = GeneratePatterns(2, 14);
            //create the SortTimes object and sort them
            dis.AddData(new RunTimes(StringMatch.MatchAlgorithms.NaiveMatcher.Match, patterns, text));
            dis.AddData(new RunTimes(StringMatch.MatchAlgorithms.Rabin_Karp.Match, patterns, text));
            dis.AddData(new RunTimes(StringMatch.MatchAlgorithms.Knuth_Morris_Pratt.Match, patterns, text));
            dis.AddData(new RunTimes(StringMatch.MatchAlgorithms.FiniteAutomaton.Match, patterns, text));
            //add data to the display

            return dis;
        }

        private static string[] GeneratePatterns(int start, int end)
        {
            string[] result = new string[end - start + 1];

            for (int i = start; i <= end; i++)
            {
                System.Threading.Thread.Sleep(200);
                result[i-start] = GenerateText(i);
                
            }

            return result;
        }

        /// <summary>
        /// Generates a string of the given size using the alphabet {a, b, c, d}
        /// </summary>
        /// <param name="size"></param>
        /// <returns></returns>
        private static string GenerateText(int size)
        {
            
            Random rng = new Random();
            int a = 0, b = 0, c = 0, d = 0, rand;
            StringBuilder text = new StringBuilder();
            //Randomly generate 100k uniformly distributed characters from {a, b, c, d}
            for (int i = 0; i < size; i++)
            {
                rand = rng.Next(65, 122);
                text.Append((char)rand);
                /*
                switch (rand)
                {
                    case 0:
                        a++;
                        text.Append("a");
                        break;
                    case 1:
                        b++;
                        text.Append("b");
                        break;
                    case 2:
                        c++;
                        text.Append("c");
                        break;
                    case 3:
                        d++;
                        text.Append("d");
                        break;
                    default:
                        Console.WriteLine("Error: rng spit out {0}", rand);
                        break;
                }*/
            }
            return text.ToString();
        }

        /// <summary>
        /// Generates a display containing sorting times of Merge, Quick, and Backwards Quicksorts. Arrays are of sizes 2^2, 2^4,...2^16.
        /// </summary>
        /// <returns></returns>
        public static Display GenerateSortingGraphDisplay()
        {
            Random rng = new Random();
            Display dis = new Display(Display.DisplayType.Sort);
            int[] arraySizes = { 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536 };
            int[][] unsortedArrays = new int[arraySizes.Length][];
            //generate the arrays
            for (int i = 0; i < arraySizes.Length; i++)
            {
                int[] array = new int[arraySizes[i]];

                for (int j = 0; j < arraySizes[i]; j++)
                {
                    array[j] = rng.Next(arraySizes[i] * 2);
                }
                unsortedArrays[i] = array;
            }
            //create the SortTimes object and sort them
            dis.AddData(new RunTimes(SortCompare.MergeSort.Sort, unsortedArrays));
            dis.AddData(new RunTimes(SortCompare.Quicksort.Sort, unsortedArrays));
            dis.AddData(new RunTimes(SortCompare.BackwardsQuicksort.Sort, unsortedArrays));
            //add data to the display

            return dis;
        }

        /// <summary>
        /// Generates a display containing the number of comparisons needed to find a given integer in a AVL tree and an AVL forest.
        /// </summary>
        /// <returns></returns>
        public static unsafe Display GenerateSearchingGraphDisplay()
        {
            int countToStore = 100000, countToSearch = 100;
            Node* treeRoot;
            BinarySearchForest bsf;
            Random rng = new Random();
            Display dis = new Display(Display.DisplayType.Search);
            SearchResults treeResults, forestResults;
            int[] valuesToStore = new int[countToStore];
            System.Threading.Thread.Sleep(200);
            ushort[] valuesToSearch = new ushort[countToSearch];

            //generate the values to store in the trees
            for (int i = 0; i < countToStore; i++)
                valuesToStore[i] = rng.Next();
            //and the values to search for in the trees
            for (int i = 0; i < countToSearch; i++)
                valuesToSearch[i] = (ushort)rng.Next();

            //Need to sort the array of values to search for so they show up pretty on the graph
            Array.Sort(valuesToSearch);
            
            //Generate the tree
            treeRoot = GenerateTree(valuesToStore);
            
            //search on the tree
            treeResults = RunComparisons(treeRoot,valuesToSearch);

            //free the tree
            //TreeUtil.FreeTree(treeRoot);

            //Generate the forest
            bsf = GenerateForest(valuesToStore);
            
            //search on the forest
            forestResults = RunComparisons(bsf, valuesToSearch);
            
            //add the results to the graph
            dis.AddData(forestResults, System.Windows.Forms.DataVisualization.Charting.MarkerStyle.Cross);
            //sleep for a bit to let the RNG shake out, otherwise the colors will be the same
            System.Threading.Thread.Sleep(200);
            dis.AddData(treeResults, System.Windows.Forms.DataVisualization.Charting.MarkerStyle.Circle);

            return dis;
        }

        /// <summary>
        /// Generates a SearchResult object containing the values searched for and the number of comparisons required to find them in the tree
        /// </summary>
        /// <param name="root"></param>
        /// <param name="valuesToSearch"></param>
        /// <returns></returns>
        unsafe private static SearchResults RunComparisons(Node* root, ushort[] valuesToSearch)
        {
            SearchResults sr = new SearchResults(valuesToSearch.Count(), "AVL Tree");
            //for each value in the array
            for (int i = 0; i < valuesToSearch.Count(); i++)
                //measure the number of comparisons it takes to find the value in the tree
                sr.AddResult((ushort)valuesToSearch[i], TreeUtil.MeasureComparisons((ushort)valuesToSearch[i], root));

            return sr;
        }

        /// <summary>
        /// Generates a SearchResult object containing the values searched for and the number of comparisons required to find them in the forest
        /// </summary>
        /// <param name="root"></param>
        /// <param name="valuesToSearch"></param>
        /// <returns></returns>
        unsafe private static SearchResults RunComparisons(BinarySearchForest bsf, ushort[] valuesToSearch)
        {
            SearchResults sr = new SearchResults(valuesToSearch.Count(), "AVL Forest");
            //for each value in the array
            for (int i = 0; i < valuesToSearch.Count(); i++)
                //measure the number of comparisons it takes to find the value in the forest
                sr.AddResult((ushort)valuesToSearch[i], bsf.MeasureComparisons((ushort)valuesToSearch[i]));

            return sr;
        }

        /// <summary>
        /// Generates an AVL binary search forest using the past values
        /// </summary>
        /// <param name="valuesToStore"></param>
        /// <returns></returns>
        unsafe private static BinarySearchForest GenerateForest(int[] valuesToStore)
        {
            BinarySearchForest bsf = new BinarySearchForest();
            //generate the Nodes for the forest second
            for (int i = 0; i < valuesToStore.Count(); i++)
            {
                Node* n         = (Node*)System.Runtime.InteropServices.Marshal.AllocHGlobal(sizeof(Node));
                n->_value       = (ushort)valuesToStore[i];
                n->_left        = null;
                n->_right       = null;
                n->_height      = 1;

                //fill the tree
                bsf.AVLAdd(n);
            }

            return bsf;
        }
        
        /// <summary>
        /// Generates an AVL binary search tree using the passed values
        /// </summary>
        /// <param name="valuesToStore"></param>
        /// <returns></returns>
        unsafe private static Node* GenerateTree(int[] valuesToStore)
        {
            Node* root = null;
            //generate the Nodes to add to the tree first
            for (int i = 0; i < valuesToStore.Count(); i++)
            {
                Node* n         = (Node*)System.Runtime.InteropServices.Marshal.AllocHGlobal(sizeof(Node));
                n->_value       = (ushort)valuesToStore[i];
                n->_left        = null;
                n->_right       = null;
                n->_height      = 1;

                //fill the tree
                SearchCompare.TreeUtil.AVLAdd(n, ref root);
            }
            return root;
        }

    }
}
